package woa.tree.binary;

/**
 * 从前序与中序遍历序列构造二叉树
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 *
 * @author wangpeng
 * @date 2021/12/4
 */
public class BuildTree2 {

    static int[] inorderArr;
    static int[] preorderArr;
    static int p = 0;


    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderArr = inorder;
        preorderArr = preorder;
        return dfs(0, inorder.length -  1);
    }

    public static TreeNode dfs(int m, int n) {
        if (m > n) {
            return null;
        }
        int i = 0;
        while (i <= n) {
            if (inorderArr[i] == preorderArr[p]) {
                break;
            }
            ++i;
        }
        ++p;
        TreeNode root = new TreeNode(inorderArr[i]);
        root.left = dfs(m, i - 1);
        root.right = dfs(i + 1, n);

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = buildTree(new int[]{-1}, new int[]{-1});
        System.out.println(root);
    }
}
